package 打牢基础30天.day02.my;

import 打牢基础30天.util.ArrUtil;

/**
 * @Author yaya
 * @Create 2024/6/12 20:52
 * Description:
 */
public class Code03_HeapSort {
    /**
     * 堆排序
     * @param arr
     */
    public static void heapSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }

        // 先全部按照大根堆进行排序
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int size = arr.length;
        swap(arr,0,--size);
        while (size > 0){
            heapify(arr,0,size);
            swap(arr,0, --size);
        }
    }

    public static void heapSortPlus(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }

        int size = arr.length;
        swap(arr,0,--size);
        while (size > 0){
            heapify(arr,0,size);
            swap(arr,0, --size);
        }

    }


    /**
     * 插入一个值
     * @param arr
     * @param index 将下标index的数据插入数组中，使得之前的数全部组成大根堆
     */
    public static void heapInsert(int[] arr, int index){
        // 如果当前节点比父节点大，往上提
        while (arr[index] > arr[(index - 1) /2]){
            swap(arr, index, ((index - 1) /2));
            index = (index - 1) /2 ;
        }
    }

    /**
     * 检查index极其子节点，是否构成大根堆（向下查询）
     * @param arr
     * @param index
     * @param size  越界判断
     */
    public static void heapify(int[] arr, int index, int size) {
        // 左节点
        int left = index * 2 + 1;

        // 找left、right、index中哪一个最大
        while (left < size) {
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
            // 找到最大的
            largest = arr[index] < arr[largest] ? largest : index;

            // 如果当前index是最大的，那就不用再往下换
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            // 往下继续换
            index = largest;
            left = index * 2 + 1;
        }
    }


    /**
     * 交换
     *
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = ArrUtil.generateRandomArray(maxSize, maxValue);
            int[] arr2 = ArrUtil.copyArray(arr1);
            heapSort(arr1);
            ArrUtil.comparator(arr2);
            if (!ArrUtil.isEqual(arr1, arr2)) {
                succeed = false;
                break;
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("costTime:"+(endTime - startTime) + "ms");

        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = ArrUtil.generateRandomArray(maxSize, maxValue);
        ArrUtil.printArray(arr);
        heapSort(arr);
        ArrUtil.printArray(arr);
    }
}
